//
// Created by Administrator on 2022/2/4.
//

#ifndef CPP_LEARNING_LEETCODE103_H
#define CPP_LEARNING_LEETCODE103_H
#include "treenode.h"
#include <vector>
using namespace std;
class Solution103 {
public:
    // [l,r]
    void zigzagLevelOrderHelper(vector<vector<int>>& result,vector<TreeNode*>& nodeLists,  bool shouldReverse){
        if(nodeLists.empty()) return;
        vector<int> valOneLevel;
        if(shouldReverse){
            for(int j=nodeLists.size()-1; j>=0; j--){
                valOneLevel.push_back(nodeLists[j]->val);
            }
            result.push_back(valOneLevel);
        }else{
            for(int i=0; i<nodeLists.size(); i++){
                valOneLevel.push_back(nodeLists[i]->val);
            }
            result.push_back(valOneLevel);
        }

        vector<TreeNode*> childNodeLists;
        for(int i=0;i<nodeLists.size(); i++){
            if(nodeLists[i]->left){
                childNodeLists.push_back(nodeLists[i]->left);
            }
            if(nodeLists[i]->right){
                childNodeLists.push_back(nodeLists[i]->right);
            }
        }
        zigzagLevelOrderHelper(result,childNodeLists,  !shouldReverse);
    }

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        vector<TreeNode*> nodeLists;
        if(root){
            nodeLists.push_back(root);
            zigzagLevelOrderHelper(result,nodeLists,  false);
        }
        return result;
    }
};

void test103(){

}
#endif //CPP_LEARNING_LEETCODE95_H
